package Z.dailyExercise.holiday;

import java.util.*;

public class _1337_矩阵中战斗力最弱的K行 {

    /**
     * 自解：用一个map存每一行的1
     * key对应行的索引 value对应这一行的1
     * 实现sort函数
     *
     * ==24%
     * @param mat
     * @param k
     * @return
     */
    public int[] kWeakestRows(int[][] mat, int k) {

        Map<Integer,Integer> map = new HashMap<>();
        for (int i=0;i<mat.length;i++){

            int value=0;
            for (int num:mat[i]){

                if (num==1){
                    value++;
                }else {
                    break;
                }
            }
            map.put(i,value);
        }


        List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                if (o1.getValue()==o2.getValue()){
                    return o1.getKey()-o2.getKey();
                }else {
                    return o1.getValue()-o2.getValue();
                }
            }
        });
        int[] res = new int[k];
        int index =0;
        while (index<k){
            res[index] = list.get(index).getKey();
            index++;



        }

        return res;

    }


    /**
     * 题解：不用map存 而是将1的数量和对应索引进行数学关联
     * 1的数量*10的k次幂+index（此题中因为mn均小于100，所以这个乘100 1000都可以）
     * 将每一行的士兵数量x1000+索引存到一个新的列表里，然后对这个列表进行排序，取前面的k位对1000取余即是需要的索引值
     */
    public int[] kWeakestRows1(int[][] mat, int k){
        int[] list = new int[mat.length];
        int[] res = new int[k];

        for (int i=0;i<mat.length;i++){
            list[i] = count(mat[i])*100+i;
        }
        Arrays.sort(list);

        for (int i=0;i<k;i++){
            res[i]= list[i]%100;
        }

        return res;


    }
    public int count(int[] num){

        int count=0;
        for (int n:num){
            if (n==1){
                count++;
            }else {
                break;
            }
        }

        return count;
    }

}
